package com.hard;


//https://leetcode.cn/problems/permutation-sequence/solutions/285250/pai-lie-zu-he-zhi-di-kge-pai-lie-golden-monkey-by-/
//https://leetcode.cn/problems/permutation-sequence/solutions/257761/hui-su-fa-neng-guo-by-yao-97/
public class Solution60 {
    boolean[] used;
    StringBuffer sb = new StringBuffer();

    public String getPermutation(int n, int k) {
        used = new boolean[n + 1];
        return back(n, k, 0);
    }

    public String back(int n, int k, int depth) {
        if (depth == n) {
            return sb.toString();
        }
        int cur = factorial(n - depth - 1);
        for (int i = 1; i <= n; i++) {
            if (used[i]) continue;
            if (cur < k) {
                k -= cur;
                continue;
            }
            sb.append(i);
            used[i] = true;
            return back(n, k, depth + 1);
        }
        return null;
    }

    public int factorial(int n) {
        int res = 1;
        while (n > 0) {
            res *= n--;
        }
        return res;
    }
}
